#include <vector>
#include <queue>
using namespace std;
/*
 * @lc app=leetcode.cn id=23 lang=cpp
 *
 * [23] 合并K个升序链表
 */

// @lc code=start
// struct ListNode {
//     int val;
//     ListNode *next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
// };

struct cmp {
    bool operator()(ListNode *n1, ListNode *n2) {
        return n1->val > n2->val;
    }
};



class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != nullptr)
                q.push(lists[i]);
        }
        ListNode node; ListNode *cur = &node;
        while (!q.empty()) {
            auto x = q.top(); q.pop();
            if (x != nullptr) {
                cur->next = x; cur = cur->next;
                x = x->next;
                if (x != nullptr) q.push(x);
            }
        }
        return node.next;
    }

    /* 最朴素的游走指针
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode node; ListNode *cur = &node;
        while (true) {
            ListNode *t = nullptr; int res = 10005, index = 0;
            for (int i = 0; i < lists.size(); i++) {
                if (lists[i] != nullptr) {
                    if (res == 10005 || res > lists[i]->val) {
                        res = lists[i]->val; t = lists[i];
                        index = i;
                    }
                }
            }
            if (t == nullptr) break;
            cur->next = t; cur = cur->next;
            lists[index] = lists[index]->next;
            
        }
        return node.next;
    }

    */


    /* 采用优先级队列优化
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != nullptr)
                q.push(lists[i]);
        }
        ListNode node; ListNode *cur = &node;
        while (!q.empty()) {
            auto x = q.top(); q.pop();
            if (x != nullptr) {
                cur->next = x; cur = cur->next;
                x = x->next;
                if (x != nullptr) q.push(x);
            }
        }
        return node.next;
    }

    */
};
// @lc code=end

